1. Field of the Invention
The present invention relates to an image data processing method and system, and more particularly to an image data processing method and system for successively giving identification labels to the individual the clusters (or areas) of connected black (or white) picture elements. The present invention is applicable to, for example, a processing for recognition of binary images.
2. Description of the Related Art
For example, in OCR (optical character reader) or drawing recognition apparatus, a labelling process for successively labelling the individual areas (or clusters) of connected black picture elements is generally performed as a preprocessing in order to extract separate characters or symbols included in image data. An example of the labelling process is illustrated in FIGS. 1A and 1B. FIG. 1A shows the original image IM.sub.O including lattice elements called picture elements. Shaded picture elements E.sub.B represent black elements and clear picture elements E.sub.W represent white elements. FIG. 1B shows one example of the result of a labelling process in which area identification numbers (or labels) are given to the areas S.sub.1 and S.sub.2 of connected black elements, respectively. A numeral "1" or "2" in each black element represents a label. The shown notation is employed for clarification of the purpose of the process though the result of labelling is not necessarily represented by the shown label table in units of one picture element. Coordinates x and y defined as shown are used in the following explanation.
A typical one of the conventional labelling methods is, for example, a method described as the prior art in Section 2.1 of the Goto et al's article entitled "High Speed Algorithm for Component Labelling", Proceedings of the Institute of Electronics, Information and Communication Engineers of Japan, D-II, Vol. 72, No. 2, pp. 247-255, February 1989. This method includes making the decision of color for every picture element in the original image IM.sub.O and examining in the case of a black element the connectivity (or condition of connection) of that black element under consideration with the surrounding element so that in the case where the black element under consideration is connected with a black element having already been provided with a certain label, the black element under consideration is provided with the same label as the certain label and in the case where the black element under consideration is further connected with a black element provided with another label, there is memorized the condition for the abovementioned or certain label and the other label that they should be the same primarily (first process). After the first process has been performed for all of the picture elements, the labels and the above-mentioned relationship of connection are examined for every picture element to correct the labels of picture elements which are provided with different labels notwithstanding that they should be provided primarily with the same label (second process). In the example shown in FIG. 1A, two black elements in the 2nd row are firstly provided with labels of different values but are relabelled in the second process so as to have the same label value.
According to the above prior art, the first process requires a processing time for decision of element color which is proportional to the total number of picture elements and a processing time for decision of connectivity which is proportional to the number of black elements, and the second process requires a processing time for decision of the presence/absence of label which is proportional to the total number of picture elements and a processing time for updating of label which is proportional to the number of black elements. Owing to these processings, for example, in the case where an image obtained by digitalizing a standard CCITT (Comite Consultatif International des Telegraphique et Telephonique) A4-size test document at 8 elements/mm is subjected to a labelling process, for example, with the Motorola 68020 microprocessor being operated at the clock of 20 MHz, the conventional labelling method requires a total processing time of several seconds to ten and several seconds.
In the case where documents or drawings are to be recognized, such a time consumed for the labelling process becomes an obstacle to the shortening of an image processing time.